package com.zhz.leetcode.sort;

import java.util.Arrays;

/**
 * 快速排序
 * <p>
 * 先随意找一个基准位   然后遍历  比它小的排左边，比他大的排右边
 * 然后递归
 * <p>
 * https://www.runoob.com/w3cnote/quick-sort-2.html
 */
public class QuickSort {

    public static void main(String[] args) {
        QuickSort m = new QuickSort();
        int[] nums = {1,6, 5, 3, 4, 2, 8, 7};
        m.sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void sort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }


    public void quickSort(int[] nums, int left, int right) {
        if (left>=right){
            return;
        }
        int pivot = nums[left];
        int low = left;
        int height = right;
        while(low<height){
            while (low<height && nums[height] >= pivot){
                height--;
            }
            nums[low] = nums[height];
            while (low<height && nums[low] <= pivot){
                low++;
            }
            nums[height] = nums[low];
        }
        nums[low] = pivot;
        quickSort(nums,left,low-1);
        quickSort(nums,low+1,right);
    }







}
